//
//  main.cpp
//  Node
//
//  Created by zhangjikuan on 2020/11/9.
//  Copyright © 2020 hsgd. All rights reserved.
//

#include <iostream>
#include <stack>
#include <string>
using namespace std;
// 使用栈设计队列
class MyQueue {
private:
    stack<int> inStack, outStack;

    void in2out() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    MyQueue() {}

    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        if (outStack.empty()) {
            in2out();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }

    int peek() {
        if (outStack.empty()) {
            in2out();
        }
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};
/* 具体地说，你的设计应该包含以下的功能

add(value)：向哈希集合中插入一个值。
contains(value) ：返回哈希集合中是否存在这个值。
remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。*/
#include <vector>
//class MyHashSet {
//
//
//public:
//    /** Initialize your data structure here. */
//    MyHashSet() {
//           hashSet = vector<bool>(10000001, false);
//       }
//
//       void add(int key) {
//           hashSet[key] = true;
//           return ;
//       }
//
//       void remove(int key) {
//           if(hashSet[key]){
//               hashSet[key] = false;
//               return ;
//           }
//           return ;
//       }
//
//       /** Returns true if this set contains the specified element */
//       bool contains(int key) {
//           return hashSet[key];
//       }
//
//
//private:
//    vector<bool> hashSet;
//};
//void my_HashSet_test ()
//{
//    MyHashSet *obj = new MyHashSet();
//
//    obj->add(1);
//    obj->add(2);
//    obj->contains(1);
//    obj->contains(3);
//    obj->add(2);
//    obj->contains(2);
//    obj->remove(2);
//    obj->contains(2);
//
//
//}

//class Bucket {
//
//};
/// 最基本的是映射 所以用光了Map key Value
/**
 所有的值都在 [0, 1000000]的范围内。
 操作的总数目在[1, 10000]范围内。
 不要使用内建的哈希库。
 */
//class MyHashMap {
//private:
//    vector<int> hasMap;
//public:
//    /** Initialize your data structure here. */
//    MyHashMap() {
//        hasMap = vector<int>(10000, -1);
//    }
//
//    /** value will always be non-negative. */
//    void put(int key, int value) {
//        hasMap[key] = value;
//        return;
//    }
//
//    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
//    int get(int key) {
//
//        return hasMap[key];
//
//    }
//
//    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
//    void remove(int key) {
//        hasMap[key] = -1;
//        return;
//    }
//};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */

class NumArray {
public:
    // 创建长度为n+1 的前缀和数组sums
    vector<int> sums;
    // 构建方法 nums 不可改变
    NumArray(vector<int> &nums) {
        long n = nums.size();
        sums.resize(n + 1);
        for (int i = 0; i < n; i ++) {
            sums[i+1] = sums[i] + nums[i];
        }
    }
    int sumRange(int i, int j) {
        // sumRange(i,j)=sums[j+1]−sums[i]
        return sums[j + 1] - sums[i];
    }
    
    // 最终采用了数学公式可以解决这个问题
};

class NumMatrix {
public:
    vector<vector<int>> matrixp;
    
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        
        matrixp.resize(m);
        for (int i = 0; i < m; i ++) {
            for (int j = n; j < n; j ++) {
                matrixp[i][j] = matrix[i][j];
            }
        }
        
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sums = 0;
        for (int i = row1; i <= row2; i ++) {
            for (int j = col1; j <= col2; j ++) {
                sums = sums + matrixp[i][j];
            }
        }

        return sums;
    }
};
#include "Solution.hpp"
static void test(vector<int> &nums, Solution &s) {
    int profit;
    nums = {1,2,3,4,5};
    
    profit = s.maxProfit(nums);
    
    cout << "profit = " << profit << endl;
    
    nums = {7,6,4,3,1};
    
    profit = s.maxProfit(nums);
    
    cout << "profit = " << profit << endl;
    
    nums = {7,1,5,3,6,4};
    
    profit = s.maxProfit(nums);
    
    cout << "profit = " << profit << endl;
    
    nums = {1,2};
    
    profit = s.maxProfit(nums);
    
    cout << "profit = " << profit << endl;
    
    // 官网
    nums = {1,2,3,4,5};
    
    profit = s.maxProfit2(nums);
    
    cout << "profit = " << profit << endl;
    
    nums = {7,6,4,3,1};
    
    profit = s.maxProfit2(nums);
    
    cout << "profit = " << profit << endl;
    
    nums = {7,1,5,3,6,4};
    
    profit = s.maxProfit2(nums);
    
    cout << "profit = " << profit << endl;
    
    nums = {1,2};
    
    profit = s.maxProfit2(nums);
    
    cout << "profit = " << profit << endl;
}
int bCount(int num) {
    int count = 0;
    while (num > 0) {
        num&=(num-1);
        count++;
    }
    return count;
}
vector<int> countBits(int num) {
//    vector<int> nums;
//    nums.resize(num + 1);
//    for (int i = 0; i <= num; i ++) {
//        cout << bCount(i) << endl;
//        nums[i] = bCount(i);
//    }
//    return nums;
//    vector<int> bits(num + 1);
//    int hightBit = 0;
//    for (int i = 1;i <= num ; i ++) {
//        if ((i & (i - 1)) == 0) {
//            hightBit = i;
//        }
//        bits[i] = bits[i - hightBit] + 1;
//        cout << bits[i] << endl;
//    }
//    return bits;
//
    vector<int> bits(num + 1);
    int highBit = 0;
    for (int i = 1; i <= num; i++) {
        if ((i & (i - 1)) == 0) {
            highBit = i;
        }
        bits[i] = bits[i - highBit] + 1;
        cout << bits[i] << endl;
    }
    return bits;
    
}
int maxEnvelopes(vector<vector<int>>& envelopes) {
    if (envelopes.empty()) {
        return 0;
    }
    
    int n = envelopes.size();
    
    sort(envelopes.begin(), envelopes.end(), [](const auto&e1, const auto& e2) {
        return e1[0] < e2[0] || (e1[0]<=e2[0] && e1[1]>e2[1]);
    });
    
    vector<int> f = {envelopes[0][1]};
    for (int i = 1; i < n; ++i) {
        if (int num = envelopes[i][1]; num > f.back()) {
            f.push_back(num);
        }
        else {
            auto it = lower_bound(f.begin(), f.end(), num);
            *it = num;
        }
    }
    return f.size();
    
}
// 最长上升子序列问题
// 方法一 动态规划 时间复杂度为O(n^2)
int lengthOfLIS(vector<int>& nums) {
    int n = (int) nums.size();
    if (n == 0) {
        return 0;
    }
    vector<int> dp(n,0);
    
    for (int i = 0; i<n; i++) {
        // 初始化状态
        dp[i] = 1;
        for (int j = 0; j<i; j++) {
            if (nums[j]<nums[i]) {
                // 更新i状态 状态转移方程
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

int minCut(string s)  {
    int n = s.size();
    vector<vector<int>> g(n, vector<int>(n, true));
    
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i + 1; j < n; ++j) {
            g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
        }
    }
    vector<int> f(n, INT_MAX);
    for (int i = 0; i < n; ++i) {
        if (g[0][i]) {
            f[i] = 0;
        }
        else {
            for (int j = 0; j < i; ++j) {
                if (g[j + 1][i]) {
                    f[i] = min(f[i], f[j] + 1);
                }
            }
        }
    }
    
    return f[n - 1];
    
}
// 删除字符串中所有相邻重复项
/**
 for (int i = 0; i < S.length - 1; i ++) {
     NSString *iS = [S substringWithRange:NSMakeRange(i, 1)];
     NSString *iAS = [S substringWithRange:NSMakeRange(i+1, 1)];
     if ([iS isEqualToString:iAS]) {
         S = [S stringByReplacingOccurrencesOfString:[NSString stringWithFormat:@"%@%@", iS,iAS] withString:@""];
         S = [self removeDuplicates:S];
         break;
     }
 }
 
 return S;
 */
string removeDuplicates(string S) {
    vector<int> nums;
    // 好简洁的思想
    string stk;
    for (char ch : S) {
        if (!stk.empty() && stk.back() == ch) {
            stk.pop_back();
        } else {
            stk.push_back(ch);
        }
    }
    return stk;
}

// 实现简单的计算器
int calculate(string s){
    stack<int> ops;
    ops.push(1);
    int sign = 1;
    int ret = 0;
    long n = s.length();
    int i = 0;
    while (i < n) {
        if (s[i] == ' ') {
            i++;
        } else if(s[i] == '+') {
            sign = ops.top();
            i++;
        } else if (s[i] == '-') {
            sign = -ops.top();
            i ++;
        } else if (s[i] == '(') {
            ops.push(sign);
            i ++;
        } else if (s[i] == ')') {
            ops.pop();
            i ++;
        } else {
            long num = 0;
            while (i < n && s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + s[i] - '0';
                i++;
            }
            ret += sign * num;
        }
    
    }
    return ret;
}

//  struct TreeNode {
//      int val;
//      TreeNode *left;
//      TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
//  };
//
//vector<int> preorderTraversal(TreeNode* root) {
//      vector<int> result;
//      stack<TreeNode*> stk;
//      while(root!=nullptr || !stk.empty()){
//          while(root!=nullptr){
//              stk.push(root);
//              result.push_back(root->val);
//              root = root->left;
//          }
//          stk.pop();
//          root = stk.top();
//          root = root->right;
//      }
//      return result;
//
//  }

vector<int> sortArray(vector<int>& nums) {

    // 做选择排序
    vector<int> res;
    
    int n = nums.size();
    
    for (int i = 0; i < n; i ++) {
        for (int j = i + 1; j < n; j ++) {
            if (nums[i] > nums[j]) {
                swap(nums[i], nums[j]);
            }
        }
    }
    
    res = nums;
    return res;
    
}

bool isValid(string s) {
    stack<char> stk;
    int l = (int)s.length();
    for (int i = 0; i < l; i++) {
        char A = s[i];
        int AI = A - '0';
        int A1 = '[' - '0';
        int A2 = '(' - '0';
        int A3 = '{' - '0';
        int A11 = ']' - '0';
        int A22 = ')' - '0';
        int A33 = '}' - '0';
        int top ;
        if (!stk.empty()) {
            top = stk.top() - '0';
            if (AI == A11) {
                if (top == A1) {
                    stk.pop();
                    continue;
                }
            }
            if (AI == A22) {
                if (top == A2) {
                    stk.pop();
                    continue;
                }
            }
            if (AI == A33) {
                if (top == A3) {
                    stk.pop();
                    continue;
                }
            }

        }
        stk.push(s[i]);
    }
    
    return stk.empty();
}
int removeElement(vector<int>& nums, int val) {
    int n =(int)nums.size();
     int len = n+1;
     for (int i = 0; i < n; i ++) {
         if (nums[i] == val) {
             // for (int j = i; j < n - 1; j++) {

             //     nums[j] = nums[j+1];
             // }
             int tmp = nums[n-i-1];
             nums[n-i-1] = val;
             nums[i] = tmp;
             
             nums[n-1] = val;
             len --;
         }
     }
  
     return len;
}
// 时间复杂度O(n * size(integer))
#include"string"
#include"algorithm"
#define MAXSIZE  500
#include "Tree.hpp"

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    
    // 开辟 m*n 的空间
    vector<vector<int>> result = matrix;
    
    for (int i = 0; i<m; i ++) {     // m
        for (int j = 0; j < n; j++) { // n          m * n
            if (result[i][j] == 0) {
                for (int k = 0; k < m; k ++) { // m
                    matrix[k][j] = 0;
                }
                for (int l = 0; l < n; l++) { // n
                    matrix[i][l] = 0;
                }
            }
        }
    }
}
int hammingWeight(uint32_t n) {
    int ret = 0;
    for (int i = 0; i < 32; i++) {
        if (n && (n << i)) {
            ret ++;
        }
    }
    return ret;
}
#include <set>
bool find132pattern(vector<int>& nums) {
    int n = nums.size();
    if (n < 3) {
        return false;
    }

    // 左侧最小值
    int left_min = nums[0];
    // 右侧所有元素
    multiset<int> right_all;

    for (int k = 2; k < n; ++k) {
        right_all.insert(nums[k]);
    }
    for (int j = 1; j < n - 1; ++j) {
              if (left_min < nums[j]) {
                  auto it = right_all.upper_bound(left_min);
                  if (it != right_all.end() && *it < nums[j]) {
                      return true;
                  }
              }
              left_min = min(left_min, nums[j]);
              right_all.erase(right_all.find(nums[j + 1]));
          }
    return false;
}

int findMaxLength(vector<int> & nums) {
    int maxLength = 0;
    unordered_map<int, int> mp;
    int counter = 0;
    mp[counter] = - 1;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int num = nums[i];
        if (num == 1) {
            counter ++;
        } else {
            counter --;
        }
        if (mp.count(counter)) {
            int preIndex = mp[counter];
            maxLength = max(maxLength, i - preIndex);
        } else {
            mp[counter] = i;
        }
    }
    return maxLength;
}

int main(int argc, const char * argv[]) {

    vector<int>removes = {0,1,2,2,3,0,4,2};
    removeElement(removes, 2);
    
    if (isValid("([](){}{([])})")){
        cout << "sucess" << endl;
    } else {
        cout << " NOT sucess" << endl;

    };
    
    
    vector<int> nums0 = {10,9,2,5,3,7,101,18};
    vector<int> res = sortArray(nums0);
    
    for (auto &&i : nums0) {
        cout << "i" << i << endl;
    }
    
    string S = "abbaca";
    
    S = removeDuplicates(S);
    
    cout << "S:" << S << endl;
    
    vector<int> LISNums = {10,9,2,5,3,7,101,18};
    int LIS = lengthOfLIS(LISNums);
    cout << "LIS:" << LIS << endl;
    //
    // auto 用法
    // auto的原理就是根据后面的值，来自己推测前面的类型是什么
    vector<int>v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    for(auto i : v){
        cout<<i<<" "<<endl;
    }
    cout<<endl;

    // 二进制优化转换
    countBits(2);
    countBits(5);

    // 区域和检索 - 数组不可变
    vector<int> numsA = {-2,0,3,-5,2,-1};
    NumArray *numArray = new NumArray(numsA);
    numArray->sumRange(0, 2); // return 1 ((-2) + 0 + 3)
    
    cout << "区域检索[0,2]" << numArray->sumRange(0, 2) << endl;
    cout << "区域检索[2,5]" << numArray->sumRange(2, 5) << endl;
    cout << "区域检索[0,5]" << numArray->sumRange(0, 5) << endl;
    cout << "区域检索[0,4]" << numArray->sumRange(0, 4) << endl;

//    my_HashSet_test();
    Solution s = Solution();
    vector<vector<int>> vc0 = {{1,2,3},{4,5,6},{7,8,9}};
    
    vector<int> order = s.spiralOrder(vc0);
    
    for (int i = 0; i < order.size(); i ++) {
        cout << order[i] << endl;
        
    }
    
    cout << "转换前"<< endl;
    cout << "[[" << vc0[0][0] << "," << vc0[0][1] << "," << vc0[0][2] << "]"<<endl;
    cout << "[" << vc0[1][0] << "," << vc0[1][1] << "," << vc0[1][2] << "]"<<endl;
    cout << "[" << vc0[2][0] << "," << vc0[2][1] << "," << vc0[2][2] << "]]"<<endl;

    cout << "转换后"<< endl;
    vc0 = s.transpose(vc0);
    cout << "[[" << vc0[0][0] << "," << vc0[0][1] << "," << vc0[0][2] << "]"<<endl;
    cout << "[" << vc0[1][0] << "," << vc0[1][1] << "," << vc0[1][2] << "]"<<endl;
    cout << "[" << vc0[2][0] << "," << vc0[2][1] << "," << vc0[2][2] << "]]"<<endl;


//    cout << s.isMatch("aaa", "a*.") << endl;
  
    vector<int> nums = {0,0,1,1,1,2,2,3,3,4};
    
    int length = s.removeDuplicates(nums);
    cout << "length = " << length << endl;
    for (int i = 0; i<length; i++) {
        cout << i << endl;
    }
    
    test(nums, s);
    
    vector<int> nums2 = {2,2,3,3,9};
//    nums2.insert(nums2.begin(), 8);
    s.plusOne(nums2);
    for (int num : nums2) {
        cout << "插入后：" << num << endl;
    }

    int ret = s.singleNumber(nums2);
    
    cout << "单数" << ret << endl;
    
    vector<int> nums3 = {0,1,0,3,12};

    s.moveZeroes(nums3);
    for (int num : nums3) {
        cout << "移动0后" << num << endl;
    }
    
    vector<string> line1 = {"8","3",".",".","7",".",".",".","."};
    
    vector< vector<string> > bo = {
    {"8","3",".",".","7",".",".",".","."},
    {"6",".",".","1","9","5",".",".","."},
    {".","9","8",".",".",".",".","6","."},
    {"8",".",".",".","6",".",".",".","3"},
    {"4",".",".","8",".","3",".",".","1"},
    {"7",".",".",".","2",".",".",".","6"},
    {".","6",".",".",".",".","2","8","."},
    {".",".",".","4","1","9",".",".","5"},
    {".",".",".",".","8",".",".","7","9"}
    };
    vector<vector<int>> vc = {
        { 5, 1, 9,11},
        { 2, 4, 8,10},
        {13, 3, 6, 7},
        {15,14,12,16}
    };

    s.rotate(vc);
    
    
    vector<char> str;
    str.push_back('h');
    str.push_back('e');
//    str.push_back('l');
//    str.push_back('l');
//    str.push_back('o');
//    str.push_back('w');

    s.reverseString(str);
    
    for (char c : str) {
        cout << c << endl;
    }
    
    int mmm = 12345678988899;
    
    cout << s.reverse(mmm) << endl;
    
    string str2 = "hellow";
    
    cout << str2[0] << str2[1] << endl;
    
    for (char c : str2) {
        cout << "HHa" << c << endl;

    }
    
    string OP = "OP";
    
    cout << s.isPalindrome(OP) << endl;
    
    string haystack = "mississippi";
    string needle = "issip";
    
    cout << s.strStr(haystack, needle) << endl;
    
//    haystack = "hello";
//    needle = "ll";
    
    cout << s.strStrKMP(haystack, needle) << endl;
    
    // 快指针和慢指针
    //
    int start = 0;
    int index = -1;
//
//    "mississippi"
//    "issip"
    
    for (int i = 0; i < haystack.length(); i ++) {
        if (haystack[i] == needle[start]) {
            index = i;
            start ++;
            if (start == needle.length()) {
                start = index - start + 1;
                
            }
        } else {
            if (start > 0) {
                i = i - start ;
                start = 0;
            }
        }
    }
    cout << s.countAndSay(1) <<endl;
    cout << s.countAndSay(2) <<endl;
    cout << s.countAndSay(3) <<endl;
    cout << s.countAndSay(4) <<endl;
    cout << s.countAndSay(5) <<endl;
    cout << s.countAndSay(6) <<endl;
    cout << s.countAndSay(7) <<endl;
    cout << s.countAndSay(8) <<endl;

    vector<int> treeArray = {1,2,2,3,4,4,3};
    
    // 递归构造
    TreeNode *root = new TreeNode(treeArray[0]);
    
    root->left = new TreeNode(treeArray[1]);
    root->right = new TreeNode(treeArray[2]);
    
    root->left->left = new TreeNode(treeArray[3]);
    root->left->right = new TreeNode(treeArray[4]);
    
    root->right->left = new TreeNode(treeArray[5]);
    root->right->right = new TreeNode(treeArray[6]);

    // 遍历一遍怎么处理
    
    TreeNodeAlgorithm treeNode = TreeNodeAlgorithm();
    
    cout << treeNode.isSymmetric(root) << endl;
    

    return 0;
}

TreeNode * constructBTree (vector<int> nums) {
    
    TreeNode *root = new TreeNode(nums[0]);
    
    
    return root;
}

struct Node {
    Node *next;
    
};


// 如何快速的求
// 求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，
// 以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。
//具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。
// 在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示。
/*
     i  next[2] = 0
 [a][b][a][b][a][b][c][a]
    [a][b][a][b][a][b][c][a]
     j

        (A)
 
 i = i + 1
 
       i next[3] = 1
[a][b][a][b][a][b][c][a]
      [a][b][a][b][a][b][c][a]
       j
 
        (B)
  
 i = i + 1
 j = j + 1
      
          i next[4] = 2
[a][b][a][b][a][b][c][a]
      [a][b][a][b][a][b][c][a]
          j
        (C)

 重复 C上的移动     next[5] = 3
                i next[6] = 4
[a][b][a][b][a][b][c][a]
      [a][b][a][b][a][b][c][a]
                j
        (D)

 
                   i next[7] = 0
[a][b][a][b][a][b][c][a]
                  [a][b][a][b][a][b][c][a]
                   j
        (D)
     i next [1] = 1
 [l][l]
    [l][l]
     j
 */

void getNext(char *p, int *next) {
    next[0]  = - 1;
    int i = 0, j = -1;
    
    while (i < strlen(p)) {
        if (j == - 1 || p[i] == p[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else
            j = next[j];
    }
}
// 双指针/从后往前
void merge(vector<int> & nums1, int m, vector<int> &nums2, int n) {
    //  足够的空间 m + n
    int tail = m+n - 1, tail1 = m - 1, tail2 = n - 1;
    
    while (tail!=tail1) { // 当tail 和tail1 不相等的时候 比较 数组1和数组2从后开始的元素，然后赋值给相应的位置
        if(tail1>=0 && nums1[tail1]>nums2[tail2]) nums1[tail--] = nums1[tail1--];
        else nums1[tail--]=nums2[tail2--];
    }
}

//[-2,1,-3,4,-1,2,1,-5,4]

// 数组 分而治之 动态规划
int maxSubArray(vector<int>& nums) {
    
    
    return 0;
}


// LC 打家劫舍
int rob(vector<int>& nums) {
    /**
  状态转移，状态转移方程
     dp[i]=max(dp[i−2]+nums[i],dp[i−1])
     dp[0]=nums[0]
     
     */
    if (nums.empty()) {
        return 0;
    }
    int size = nums.size();
    if (size == 1) {
        return nums[0];
    }
    int first = nums[0], second = max(nums[0], nums[1]);
    for (int i = 2; i < size; i++) {
        int temp = second;
        second = max(first + nums[i], second);
        first = temp;
    }
    return second;
}


string intToRoman(int num) {
    string mString;
    for (int i = 0; i<num/1000; i++) {
        mString.append("M");
    }
    
    num = num%1000;
    
    // num = 900 和 num = 400
    int bNum = num/100;
    if (bNum == 9) {
        mString.append("CM");
    } else if (bNum > 4 && bNum < 9) {
        mString.append("D");
        for (int i = 0; i< bNum - 5; i ++) {
            mString.append("C");
        }
    } else if (bNum == 4) {
        mString.append("CD");
    } else {
        for (int i = 0; i<bNum; i++) {
            mString.append("C");
        }
    }
    
    num = num%100;
    bNum = num/10;
    if (bNum == 9) {
        mString.append("XC");
    } else if (bNum > 4 && bNum < 9) {
        mString.append("L");
        for (int i = 0; i< bNum - 5; i ++) {
            mString.append("X");
        }
    } else if (bNum == 4) {
        mString.append("XL");
    } else {
        for (int i = 0; i<bNum; i++) {
            mString.append("X");
        }
    }
    
    num = num%10;
    bNum = num;
    
    if (bNum == 9) {
        mString.append("IX");
    } else if (bNum > 4 && bNum < 9) {
        mString.append("V");
        for (int i = 0; i< bNum - 5; i ++) {
            mString.append("I");
        }
    } else if (bNum == 4) {
        mString.append("IV");
    } else {
        for (int i = 0; i<bNum; i++) {
            mString.append("I");
        }
    }
    
    
    return mString;
}
//string intToRoman(int num) {
//    vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
//    vector<string> symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
//    string result;
//
//
//    for (int i = 0; i < values.size() && num >=0; i++) {
//        while (values[i] <= num) {
//            num -= values[i];
//            result.append(symbols[i]);
//        }
//    }
//
//    return result;
//}
//int romanToInt(string s) {
//
//
// }
